class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        //思路：第i为整除k为r，找前0-i-1位置有多少个整除k为r加上来
        //   前面出现的整除r的余数，出现次数
        unordered_map<int,int> hash;
        hash[0]=1;              //防止第i个刚好和被k整除

        int sum=0,ret=0;        //当前前缀和，记录总个数
        for(auto x:nums)
        {
            sum+=x;                 //前缀和
            int r=((sum%k)+k)%k;    //负数修正
            if(hash.count(r))       //前0-i-1位置有多少个sum-k
                ret+=hash[r];       //统计个数
            
            //把余数为r加入
            hash[r]++;
        }
        return ret;
    }
};